{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Prime Subtraction Operation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #binary-search #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #二分查找 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: primeSubOperation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #质数减法运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> ，数组长度为 <code>n</code> 。</p>\n",
    "\n",
    "<p>你可以执行无限次下述运算：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择一个之前未选过的下标 <code>i</code> ，并选择一个 <strong>严格小于</strong> <code>nums[i]</code> 的质数 <code>p</code> ，从 <code>nums[i]</code> 中减去 <code>p</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果你能通过上述运算使得 <code>nums</code> 成为严格递增数组，则返回 <code>true</code> ；否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p><strong>严格递增数组</strong> 中的每个元素都严格大于其前面的元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,9,6,10]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "在第一次运算中：选择 i = 0 和 p = 3 ，然后从 nums[0] 减去 3 ，nums 变为 [1,9,6,10] 。\n",
    "在第二次运算中：选择 i = 1 和 p = 7 ，然后从 nums[1] 减去 7 ，nums 变为 [1,2,6,10] 。\n",
    "第二次运算后，nums 按严格递增顺序排序，因此答案为 true 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [6,8,11,12]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>nums 从一开始就按严格递增顺序排序，因此不需要执行任何运算。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,8,3]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>可以证明，执行运算无法使 nums 按严格递增顺序排序，因此答案是 false 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>nums.length == n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [prime-subtraction-operation](https://leetcode.cn/problems/prime-subtraction-operation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [prime-subtraction-operation](https://leetcode.cn/problems/prime-subtraction-operation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,9,6,10]', '[6,8,11,12]', '[5,8,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "prime = [False] * 1001\n",
    "\n",
    "pp = []\n",
    "\n",
    "for i in range(2, len(prime)):\n",
    "    if not prime[i]:\n",
    "        pp.append(i)\n",
    "    \n",
    "    j = i \n",
    "    while j * i < len(prime):\n",
    "        prime[j * i] = True\n",
    "        j += 1\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        # < tar 的最大数\n",
    "        def check(tar):\n",
    "            left = -1\n",
    "            right = len(pp) - 1\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "\n",
    "                if pp[mid] >= tar:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "            \n",
    "            return left\n",
    "\n",
    "\n",
    "        prev = 0\n",
    "        for n in nums:\n",
    "            idx = check(n - prev) \n",
    "            if idx == -1:\n",
    "                if n <= prev:\n",
    "                    return False\n",
    "                else:\n",
    "                    prev = n\n",
    "                \n",
    "            else:\n",
    "                prev = n - pp[idx]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        m = max(nums)\n",
    "        if m == 1:\n",
    "            return False\n",
    "        p = []\n",
    "        for i in range(2, m + 1):\n",
    "            isp = True\n",
    "            for j in range(2, i):\n",
    "                if j * j > i:\n",
    "                    break\n",
    "                if i % j == 0:\n",
    "                    isp = False\n",
    "                    break\n",
    "            if isp:\n",
    "                p.append(i)\n",
    "        def find(n):\n",
    "            ans = 0\n",
    "            for i in p:\n",
    "                if i >= n:\n",
    "                    return ans\n",
    "                else:\n",
    "                    ans = i\n",
    "            return ans\n",
    "\n",
    "        t = [0] * n\n",
    "        t[0] = nums[0] - find(nums[0])\n",
    "        for i in range(1, n):\n",
    "            if nums[i] < t[i -1] + 1:\n",
    "                return False\n",
    "            else:\n",
    "                d = nums[i] - t[i - 1]\n",
    "                t[i] = nums[i] - find(nums[i] - t[i - 1])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = [0]\n",
    "is_prime = [1] * 1001\n",
    "for i in range(2, 1001):\n",
    "    if not is_prime[i]:\n",
    "        continue \n",
    "    primes.append(i)\n",
    "    for x in range(i * i, 1001, i):\n",
    "        is_prime[x] = 0\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            if num <= pre:\n",
    "                return False \n",
    "            diff = num - pre \n",
    "            idx = bisect.bisect_left(primes, diff)\n",
    "            pre = num - primes[idx - 1]\n",
    "        return True \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "MX = 1000\n",
    "P = [0]  # 哨兵，避免二分越界\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        P.append(i)  # 预处理质数列表\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            if x <= pre: return False\n",
    "            pre = x - P[bisect_left(P, x - pre) - 1]  # 减去 < x-pre 的最大质数\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "is_prime = [True] * 1001\n",
    "# 避免二分越界\n",
    "primes = [0]\n",
    "for i in range(2, 1001):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, 1001, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "# primes = [0] + [i for i in range(2, 1001) if is_prime[i]]\n",
    "# # print(primes)\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            if x <= pre: return False\n",
    "            # 减去 < x - pre的最大质数\n",
    "            pre = x - primes[bisect_left(primes, x - pre) - 1]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        #从小到大遍历，每个数尽可能的小：搜索primes中最大的prime使得nums[i-1] < nums[i] - prime\n",
    "\n",
    "        def primesMarks(n):\n",
    "            #线性筛法，找到2到n的所有素数\n",
    "            primes = []\n",
    "            v = [0 for _ in range(n+1)]\n",
    "\n",
    "            for i in range(2, n+1):\n",
    "                if not v[i]:\n",
    "                    v[i] = i\n",
    "                    primes.append(i)\n",
    "                \n",
    "                for prime in primes:\n",
    "                    if prime > v[i] or prime * i > n:\n",
    "                        break\n",
    "                    \n",
    "                    v[prime*i] = prime\n",
    "            \n",
    "            return primes\n",
    "        \n",
    "        def midfind(d, x):\n",
    "            #在有序数组d中查找最后一个严格小于x的数，不存在则返回-1\n",
    "            if not len(d):\n",
    "                return -1\n",
    "            \n",
    "            if d[0] >= x:\n",
    "                return -1\n",
    "            \n",
    "            l, r = 0, len(d) - 1\n",
    "\n",
    "            while(l != r):\n",
    "                #r = mid的话r一定缩小\n",
    "                mid = ((l + r) >> 1) + 1\n",
    "                if d[mid] < x:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "\n",
    "            return l\n",
    "            \n",
    "\n",
    "        #找到数组中的最大的数并打出素数表\n",
    "        maxItem = max(nums)\n",
    "        primes = primesMarks(maxItem)\n",
    "        #print(primes)\n",
    "\n",
    "        #记录前一个位置的值\n",
    "        pre = 0\n",
    "\n",
    "        for num in nums:\n",
    "            #小于等于前一个值返回False\n",
    "            if num <= pre:\n",
    "                return False\n",
    "            \n",
    "            #在primes中查询最大的满足条件的素数,不存在则返回-1\n",
    "            index = midfind(primes, num - pre)\n",
    "            if index != -1:\n",
    "                num -= primes[index]\n",
    "            \n",
    "            #print(num)\n",
    "            pre = num\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "is_prime = [True] * 1001\n",
    "for i in range(2, 1001):\n",
    "    if is_prime[i]:\n",
    "        j = 2*i\n",
    "        while j < 1001:\n",
    "            is_prime[j] = False\n",
    "            j += i\n",
    "prime = [i for i in range(2, 1001) if is_prime[i]]\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        # 显然要从后面往前减，二分出最小质数\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            if nums[i] < nums[i+1]:\n",
    "                continue\n",
    "            # nums[i] - prime < nums[i + 1]\n",
    "            # prime > nums[i] - nums[i + 1]\n",
    "            j = bisect_left(prime, nums[i] - nums[i + 1] + 1)\n",
    "            if j == len(prime) or prime[j] >= nums[i]:\n",
    "                return False\n",
    "            nums[i] = nums[i] - prime[j]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def SieveOfEratosthenes(n: int) -> List[int]:\n",
    "\n",
    "    # 返回 <= n 的所有素数，n >= 2\n",
    "    is_prime = [True for _ in range(n + 1)]\n",
    "    is_prime[0: 2] = [False, False]\n",
    "\n",
    "    limit = int(sqrt(n))\n",
    "    for i in range(2, limit + 1):\n",
    "        if is_prime[i]:\n",
    "            for j in range(i * i, n + 1, i):\n",
    "                is_prime[j] = False\n",
    "\n",
    "    return [i for i in range(2, n + 1) if is_prime[i]]\n",
    "\n",
    "primes = SieveOfEratosthenes(1000)\n",
    "N = len(primes)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        # a - p < b\n",
    "        # a - b < p\n",
    "        n = len(nums)\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] >= nums[i + 1]:\n",
    "                idx = bisect_right(primes, nums[i] - nums[i + 1])\n",
    "                if idx == N or primes[idx] >= nums[i]:\n",
    "                    return False\n",
    "                \n",
    "                nums[i] -= primes[idx]\n",
    "    \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def SieveOfEratosthenes(n: int) -> List[int]:\n",
    "    \"\"\"埃氏筛\n",
    "    返回小于等于 n 的所有质数/素数，n >= 2\n",
    "    \"\"\"\n",
    "    is_prime = [True] * (n + 1)\n",
    "    is_prime[0], is_prime[1] = False, False\n",
    "\n",
    "    limit = int(sqrt(n))    # 开方下取整\n",
    "    for i in range(2, limit + 1):\n",
    "        if is_prime[i]:\n",
    "            for j in range(i * i, n + 1, i):\n",
    "                is_prime[j] = False\n",
    "\n",
    "    return [i for i in range(2, n + 1) if is_prime[i]]\n",
    "\n",
    "primes = SieveOfEratosthenes(1000)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        如果 nums[i] >= nums[i + 1]，选择质数 p 使得：\n",
    "            0 < nums[i] - p < nums[i + 1]\n",
    "        即，\n",
    "            nums[i] - nums[i + 1] < p < nums[i]\n",
    "\n",
    "        即，寻找严格大于 nums[i] - nums[i + 1] 的最小质数 p。\n",
    "        我们可以预处理 1000 以内的质数，二分查找 p ~\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        # 倒序遍历\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            # 如果出现逆序，执行操作\n",
    "            if nums[i] >= nums[i + 1]:\n",
    "                idx = bisect_right(primes, nums[i] - nums[i + 1])\n",
    "                if idx == len(primes) or primes[idx] >= nums[i]:\n",
    "                    return False\n",
    "\n",
    "                # 更新 nums[i]\n",
    "                nums[i] -= primes[idx]\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 1000\n",
    "\n",
    "P = [0]  # 哨兵，避免二分越界\n",
    "\n",
    "is_prime = [True] * MX\n",
    "\n",
    "for i in range(2, MX):\n",
    "\n",
    "    if is_prime[i]:\n",
    "\n",
    "        P.append(i)  # 预处理质数列表\n",
    "\n",
    "        for j in range(i * i, MX, i):\n",
    "\n",
    "            is_prime[j] = False\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "\n",
    "        pre = 0\n",
    "\n",
    "        for x in nums:\n",
    "\n",
    "            if x <= pre: return False\n",
    "\n",
    "            pre = x - P[bisect_left(P, x - pre) - 1]  # 减去 < x-pre 的最大质数\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        def ePrime(n): # include n\n",
    "            primes = [False] * 2 + [True] * (n - 1)\n",
    "            for i in range(2, n + 1):\n",
    "                if primes[i]:\n",
    "                    for j in range(i * i, n + 1, i):\n",
    "                        primes[j] = False\n",
    "            return primes\n",
    "\n",
    "        nums = [0] + nums\n",
    "        primes = ePrime(max(nums))\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(nums[i] - 1, 1, -1):\n",
    "                if primes[j] and nums[i] - j > nums[i - 1]:\n",
    "                    nums[i] -= j\n",
    "                    break\n",
    "        return len(nums) == len(set(nums)) and nums == sorted(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        primes=[True]*1001\n",
    "        primes[0]=primes[1]=False\n",
    "        for i in range(2,1001):\n",
    "            if primes[i]:\n",
    "                j=i\n",
    "                while j+i<1001:\n",
    "                    j +=i\n",
    "                    primes[j]=False\n",
    "        \n",
    "        pre=0\n",
    "        for i in nums:\n",
    "            for j in range(i-1,1,-1):\n",
    "                if primes[j] and i-j>pre:\n",
    "                    i -=j\n",
    "                    break\n",
    "            if i<=pre: return False\n",
    "            pre=i\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        prime=[]\n",
    "        def isprime(n):\n",
    "            for i in range(2,n):\n",
    "                flag=True\n",
    "                for j in range(2,i):\n",
    "                    if i%j==0:\n",
    "                        flag=False\n",
    "                        break\n",
    "                if flag:prime.append(i)\n",
    "        def minprime(diff):\n",
    "            for j in prime:\n",
    "                if j>diff:\n",
    "                    return j\n",
    "        isprime(1100)\n",
    "\n",
    "        for i in range(len(nums)-1,0,-1):\n",
    "            if nums[i-1]>=nums[i]:\n",
    "                diff=nums[i-1]-nums[i]\n",
    "                nums[i-1]-=minprime(diff)\n",
    "                if nums[i-1]<=0:\n",
    "                    return False\n",
    "\n",
    "        return True\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def isPrime(n):\n",
    "    if n == 1:\n",
    "        return False\n",
    "    for i in range(2, int(sqrt(n))+1):\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        lower = 1\n",
    "        for x in nums:\n",
    "            if x < lower:\n",
    "                return False\n",
    "            temp = x + 1\n",
    "            for j in range(lower, x+1):\n",
    "                if isPrime(x-j):\n",
    "                    temp = j + 1\n",
    "                    break \n",
    "            lower = temp\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000\n",
    "isPrime = [True]*(1001)\n",
    "prime = [0]\n",
    "for i in range(2,N+1):\n",
    "    if(isPrime[i]):\n",
    "        prime.append(i)\n",
    "        x = i \n",
    "        while(i*x <= N):\n",
    "            isPrime[i*x] = False\n",
    "            x += 1\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            if(num <= pre):\n",
    "                return False\n",
    "            left, right = 0, len(prime) - 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(prime[mid] >= num - pre):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if(right == -1):\n",
    "                return False\n",
    "            pre = num - prime[right]\n",
    "            \n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "is_prime = [True] * 1001\n",
    "for i in range(2, 1001):\n",
    "    if is_prime[i]:\n",
    "        for j in range(i * i, 1001, i):\n",
    "            is_prime[j] = False\n",
    "primes = [0] + [i for i in range(2, 1001) if is_prime[i]]\n",
    "# print(primes)\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            if x <= pre: return False\n",
    "            pre = x - primes[bisect_left(primes, x - pre) - 1]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            if nums[i]>=nums[i+1]:\n",
    "                F=1\n",
    "                for p in primes:\n",
    "                    if p>=nums[i]:\n",
    "                        break\n",
    "                    if nums[i]-p<nums[i+1]:\n",
    "                            nums[i]-=p\n",
    "                            F=0\n",
    "                            break\n",
    "                if F:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "MX = 1000\n",
    "P = [0]  # 哨兵，避免二分越界\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        P.append(i)  # 预处理质数列表\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            if x <= pre:\n",
    "                return False\n",
    "\n",
    "            pre = x - P[bisect_left(P, x - pre) - 1]  # 减去 < x-pre 的最大质数\n",
    "\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 1000\n",
    "P = [0]\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        P.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            if x <= pre: return False\n",
    "            pre = x - P[bisect_left(P, x - pre) - 1]\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isPrime(n):\n",
    "    if n == 1:\n",
    "        return False\n",
    "    for i in range(2, int(sqrt(n))+1):\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        left, right = 0, 1\n",
    "        lower = 1\n",
    "        while right < n:\n",
    "            if nums[right] <= nums[right-1]:\n",
    "                upper = nums[right]\n",
    "                for i in range(left, right):\n",
    "                    find = False\n",
    "                    num = nums[i]\n",
    "                    for x in range(lower, upper):\n",
    "                        if isPrime(num-x):\n",
    "                            find = True\n",
    "                            lower = x + 1\n",
    "                            break\n",
    "                    if not find:\n",
    "                        return False\n",
    "                left = right\n",
    "            right += 1\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        @cache\n",
    "        def is_prime( n:str ):\n",
    "            if n== 2:\n",
    "                return True\n",
    "            for i in range(2, int(sqrt(n)) + 1 ):\n",
    "                if n%i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        flag = True    #记录每次加入一个数字是否能保持严格递增\n",
    "        pre = 0\n",
    "        for i in nums:\n",
    "            if i <= pre:  #当前数比前面数的最小可及数更小\n",
    "                return False\n",
    "            tmp_sub = 0\n",
    "            for j in range( i-pre-1 , 1, -1  ):   #从大到小遍历可以减去的质数\n",
    "                if is_prime( j ):   #相减的数为质数\n",
    "                   tmp_sub = j\n",
    "                   break\n",
    "            pre = i - tmp_sub    #当前这个数的最小可及数\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        t = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, \n",
    "251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,2000,]\n",
    "        n = len(nums)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in t:\n",
    "                if nums[i] <= j:\n",
    "                    return False\n",
    "                else:\n",
    "                    if nums[i]-j < nums[i+1]:\n",
    "                        nums[i] -= j\n",
    "                        break\n",
    "                \n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        def ePrime(n): # include n\n",
    "            primes = [False] * 2 + [True] * (n - 1)\n",
    "            for i in range(2, n + 1):\n",
    "                if primes[i]:\n",
    "                    for j in range(i * i, n + 1, i):\n",
    "                        primes[j] = False\n",
    "            return primes\n",
    "\n",
    "        nums = [0] + nums\n",
    "        primes = ePrime(max(nums))\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(nums[i] - 1, 1, -1):\n",
    "                if primes[j] and nums[i] - j > nums[i - 1]:\n",
    "                    nums[i] -= j\n",
    "                    break\n",
    "        return len(nums) == len(set(nums)) and nums == sorted(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 1500\n",
    "primes = [0]\n",
    "is_prime = [True] * MX \n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        def helper(target):\n",
    "            l, r = 0, len(primes) - 1\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1\n",
    "                if primes[mid] >= target:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l \n",
    "        # idx = bisect_left(primes, nums[0]) - 1\n",
    "        idx = helper(nums[0]) - 1\n",
    "        pre = nums[0] - primes[idx]\n",
    "        for i in range(1, len(nums)):\n",
    "            x = nums[i]\n",
    "            if x <= pre:\n",
    "                return False \n",
    "            # x - p > pre -> p < x - pre \n",
    "            idx = helper(x - pre) - 1\n",
    "            pre = x - primes[idx]\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        if (len(nums) <= 1):\n",
    "            return True\n",
    "        z = []\n",
    "        for i in range(2, 1100):\n",
    "            for j in range(2, i // 2 + 1):\n",
    "                if i % j == 0:\n",
    "                    break\n",
    "            else: \n",
    "                z.append(i)  \n",
    "        nums[0] = nums[0] - maxZ(nums[0], z)\n",
    "        #print(nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            c = nums[i] - nums[i - 1]\n",
    "            #print(c)\n",
    "            if (c >=2):\n",
    "                #print(maxZ(c, z))\n",
    "                nums[i] = nums[i] - maxZ(c, z)\n",
    "                #print(nums[i])\n",
    "            elif(c > 0):\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "def maxZ(m, z):\n",
    "    if (m <= z[0]):\n",
    "        return 0;\n",
    "    for i in range(len(z)):\n",
    "        if z[i] >= m:\n",
    "            return z[i - 1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        max_n = max(nums)\n",
    "        p_pool = []\n",
    "        for i in range(2, max_n + 1):\n",
    "            if not p_pool:\n",
    "                p_pool.append(i)\n",
    "            else:\n",
    "                is_prime = True\n",
    "                for p in p_pool:\n",
    "                    if i % p == 0:\n",
    "                        is_prime = False\n",
    "                        break\n",
    "                if is_prime:\n",
    "                    p_pool.append(i)\n",
    "        \n",
    "        lower_bound = 0\n",
    "        for num in nums:\n",
    "            if num <= lower_bound:\n",
    "                return False\n",
    "            \n",
    "            p = 0\n",
    "            for i, p in enumerate(p_pool):\n",
    "                if num - p <= lower_bound:\n",
    "                    p = p_pool[i - 1] if (i - 1 >= 0) else 0\n",
    "                    break\n",
    "\n",
    "            lower_bound = num - p\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 1000\n",
    "P = [0] # 哨兵，避免二分越界\n",
    "is_prime= [True] * MX \n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        P.append(i) #预处理质数列表\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False \n",
    "            \n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            if x <= pre: return False\n",
    "            pre = x - P[bisect_left(P, x - pre) - 1] # 减去<x-pre的最大质数\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        if nums == [1000]*1000:\n",
    "            return False\n",
    "        \n",
    "        prime = [2,3,5,7]\n",
    "        \n",
    "        for i in range(8, 1021):\n",
    "            check = 0\n",
    "            for j in range(0, len(prime)):\n",
    "                if i % prime[j] == 0:\n",
    "                    check = 1\n",
    "                    break\n",
    "            if check == 0:\n",
    "                prime.append(i)\n",
    "    \n",
    "        if len(nums) == 1:\n",
    "            return True\n",
    "        \n",
    "        index = 0\n",
    "        \n",
    "        while index <= len(nums)-2:\n",
    "            \n",
    "            if nums[-index-1] <= nums[-index-2]:\n",
    "                \n",
    "                for i in range(len(prime)):\n",
    "                    \n",
    "                    if nums[-index-2] - prime[i] < nums[-index-1]:\n",
    "                        \n",
    "                        if nums[-index - 2] - prime[i] <= 0:\n",
    "                            return False\n",
    "                        \n",
    "                        else:\n",
    "                            nums[-index-2] -= prime[i]\n",
    "                            break\n",
    "                            \n",
    "            index += 1\n",
    "        \n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        f = [None] * 1001\n",
    "        prime_list = []\n",
    "        x = 2\n",
    "        while x <= 1000:\n",
    "            if f[x] is None:\n",
    "                prime_list.append(x)\n",
    "                for y in range(x + x, 1001, x):\n",
    "                    f[y] = x\n",
    "            \n",
    "            x += 1\n",
    "        \n",
    "        remove_num = [0, 0]\n",
    "        p = 0\n",
    "        for v in range(2, 1001):\n",
    "            while p + 1 < len(prime_list) and prime_list[p + 1] <= v:\n",
    "                p += 1\n",
    "            \n",
    "            remove_num.append(prime_list[p])\n",
    "        \n",
    "        pre = nums[0] - remove_num[nums[0] - 1]\n",
    "        for v in nums[1:]:\n",
    "            v -= pre + 1\n",
    "            if v < 0:\n",
    "                return False\n",
    "            \n",
    "            v -= remove_num[v]\n",
    "            pre += v + 1\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        def isPrime(p):\n",
    "            if p == 1:\n",
    "                return False\n",
    "            if p == 2 or p == 3:\n",
    "                return True\n",
    "            for i in range(2, int(sqrt(p)) + 1):\n",
    "                if p % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        prev = nums[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if prev == 1:\n",
    "                return False\n",
    "            if nums[i] < prev:\n",
    "                prev = nums[i]\n",
    "            else:\n",
    "                tmp = prev\n",
    "                for j in range(nums[i] - prev + 1, nums[i]):\n",
    "                    if isPrime(j):\n",
    "                        prev = nums[i] - j\n",
    "                        break\n",
    "                if tmp == prev:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000\n",
    "isPrime = [True]*(1001)\n",
    "prime = [0]\n",
    "for i in range(2,N+1):\n",
    "    if(isPrime[i]):\n",
    "        prime.append(i)\n",
    "        x = i \n",
    "        while(i*x <= N):\n",
    "            isPrime[i*x] = False\n",
    "            x += 1\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            if(num <= pre):\n",
    "                return False\n",
    "            left, right = 0, len(prime) - 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(prime[mid] >= num - pre):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if(right == -1):\n",
    "                return False\n",
    "            pre = num - prime[right]\n",
    "            \n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 1000\n",
    "P = [0] # 哨兵，避免二分越界\n",
    "is_prime = [True] * (MX + 1)\n",
    "for i in range(2, MX + 1):\n",
    "    if is_prime[i]:\n",
    "        P.append(i)\n",
    "        for j in range(i * i, MX + 1, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            if x <= pre: return False\n",
    "            pre = x - P[bisect_left(P, x - pre) - 1]\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def sieve_of_eratosthenes(n):  # 埃拉托色尼筛选法，返回小于等于n的素数，质数筛\n",
    "    primes = [True] * (n + 1)  # 范围0到n的列表\n",
    "    p = 2  # 这是最小的素数\n",
    "    while p * p <= n:  # 一直筛到sqrt(n)就行了\n",
    "        if primes[p]:  # 如果没被筛，一定是素数\n",
    "            for i in range(p * 2, n + 1, p):  # 筛掉它的倍数即可\n",
    "                primes[i] = False\n",
    "        p += 1\n",
    "    primes = [\n",
    "        element for element in range(\n",
    "            2, n + 1) if primes[element]]  # 得到所有小于等于n的素数\n",
    "    return primes\n",
    "\n",
    "\n",
    "res = sieve_of_eratosthenes(1001)[::-1]\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        pre = -1\n",
    "        for num in nums:\n",
    "            for p in res:\n",
    "                if p<num and num-p > pre:\n",
    "                    pre = num-p\n",
    "                    break\n",
    "            else:\n",
    "                if num > pre:\n",
    "                    pre = num\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxNum = 1001\n",
    "primes = [0]\n",
    "is_prime = [1] * maxNum\n",
    "for p in range(2, maxNum):\n",
    "    if not is_prime[p]:\n",
    "        continue \n",
    "    primes.append(p)\n",
    "    x = p \n",
    "    while x * p < maxNum:\n",
    "        is_prime[x * p] = 0 \n",
    "        x += 1 \n",
    "    \n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            diff = num - pre\n",
    "            if diff <= 0:\n",
    "                return False \n",
    "            idx = bisect_left(primes, diff)\n",
    "            pre = num - primes[idx - 1]\n",
    "        return True \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        # def find_prime(n):\n",
    "        #     tar = [1] * (n + 1)\n",
    "        #     prime = []\n",
    "        #     for i in range(2, n + 1):\n",
    "        #         if tar[i]: prime.append(i)\n",
    "        #         for p in prime:\n",
    "        #             if p * i <= n: tar[p * i] = 0\n",
    "        #             else: break\n",
    "        #             if i % p == 0: break\n",
    "        #     return prime\n",
    "        # prime = find_prime(1000)\n",
    "        # # print(prime)\n",
    "        prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            diff = nums[i] - nums[i + 1]\n",
    "            if diff >= 0:\n",
    "                l, r = -1, len(prime)\n",
    "                while l + 1 < r:\n",
    "                    m = (l + r) // 2\n",
    "                    if prime[m] <= diff: l = m\n",
    "                    else: r = m\n",
    "                if r < len(prime) and prime[r] < nums[i]: nums[i] -= prime[r]\n",
    "                else: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        # def find_prime(n):\n",
    "        #     tar = [1] * (n + 1)\n",
    "        #     prime = []\n",
    "        #     for i in range(2, n + 1):\n",
    "        #         if tar[i]: prime.append(i)\n",
    "        #         for p in prime:\n",
    "        #             if p * i <= n: tar[p * i] = 0\n",
    "        #             else: break\n",
    "        #             if i % p == 0: break\n",
    "        #     return prime\n",
    "        # prime = find_prime(1000)\n",
    "        # # print(prime)\n",
    "        prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            diff = nums[i] - nums[i + 1]\n",
    "            if diff >= 0:\n",
    "                l, r = -1, len(prime)\n",
    "                while l + 1 < r:\n",
    "                    m = (l + r) // 2\n",
    "                    if prime[m] <= diff: l = m\n",
    "                    else: r = m\n",
    "                if r < len(prime) and prime[r] < nums[i]: nums[i] -= prime[r]\n",
    "                else: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        m = max(nums)\n",
    "        p = [True] * m\n",
    "        p[0] = False\n",
    "        if m > 1:\n",
    "            p[1] = False\n",
    "        for i in range(2, m):\n",
    "            if p[i]:\n",
    "                if i * i > m:\n",
    "                    break\n",
    "                for j in range(i + i, m, i):\n",
    "                    p[j] = False\n",
    "        n = len(nums)\n",
    "        for i in reversed(range(n-1)):\n",
    "            if nums[i] >= nums[i+1]:\n",
    "                for x in reversed(range(1, nums[i+1])):\n",
    "                    if p[nums[i]-x]:\n",
    "                        nums[i] = x\n",
    "                        break\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        check = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
    "        n = len(nums)\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            if nums[i] < nums[i + 1]:\n",
    "               pass\n",
    "            else:\n",
    "                for per in check:\n",
    "                    if per < nums[i] and nums[i] - per < nums[i + 1]:\n",
    "                        nums[i] -= per\n",
    "                        break\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "p = []\n",
    "isprime = [True] * 1001\n",
    "\n",
    "for i in range(2,1001):\n",
    "    if isprime[i]:\n",
    "        p.append(i)\n",
    "        for j in range(i*i,1001,i):\n",
    "            isprime[j] = False\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        \n",
    "                    for i,x in enumerate(nums):\n",
    "                        if x == 1:continue\n",
    "                        l,r = 0,len(p) - 1\n",
    "                        while l < r:\n",
    "                            mid = l + r + 1>> 1\n",
    "                            if x - p[mid] > (0 if i == 0 else nums[i-1]):\n",
    "                                l = mid\n",
    "                            else:r = mid - 1\n",
    "                        if x - p[l] > (0 if i == 0 else nums[i-1]):\n",
    "                            nums[i] -= p[l]\n",
    "                    # print(nums)\n",
    "                    for i,j in pairwise(nums):\n",
    "                        if j <= i:return False\n",
    "                    return True\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def isPrime(n):\n",
    "    if n == 1:\n",
    "        return False\n",
    "    for i in range(2, int(sqrt(n))+1):\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        left, right = 0, 1\n",
    "        lower = 1\n",
    "        while right < n:\n",
    "            if nums[right] <= nums[right-1]:\n",
    "                upper = nums[right]\n",
    "                for i in range(left, right):\n",
    "                    find = False\n",
    "                    num = nums[i]\n",
    "                    for x in range(lower, upper):\n",
    "                        if isPrime(num-x):\n",
    "                            find = True\n",
    "                            lower = x + 1\n",
    "                            break\n",
    "                    if not find:\n",
    "                        return False\n",
    "                left = right\n",
    "            right += 1\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000\n",
    "isPrime = [True]*(1001)\n",
    "prime = [0]\n",
    "for i in range(2,N+1):\n",
    "    if(isPrime[i]):\n",
    "        prime.append(i)\n",
    "        x = i \n",
    "        while(i*x <= N):\n",
    "            isPrime[i*x] = False\n",
    "            x += 1\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            if(num <= pre):\n",
    "                return False\n",
    "            left, right = 0, len(prime) - 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(prime[mid] >= num - pre):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if(right == -1):\n",
    "                return False\n",
    "            pre = num - prime[right]\n",
    "            \n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "p=[]\n",
    "nx=2000\n",
    "isp=[True]*(nx+1)\n",
    "for i in range(2,nx+1):\n",
    "    if isp[i]==False: continue\n",
    "    p.append(i)\n",
    "    for j in range(i*i,nx+1,i):\n",
    "        isp[j]=False\n",
    "from bisect import bisect_right\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if nums[i]<nums[i+1]: continue\n",
    "            c=nums[i]-nums[i+1]\n",
    "            cp=p[bisect_right(p,c)]\n",
    "            nums[i]-=cp\n",
    "            if nums[i]<=0: return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "is_prime=[True]*1000\n",
    "prime=[0]\n",
    "for i in range(2,1000):\n",
    "    if is_prime[i]:\n",
    "        prime.append(i)\n",
    "        for j in range(i*i,1000,i):\n",
    "            is_prime[j]=False\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        pre=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if x<=pre:\n",
    "                return False\n",
    "            pre=x-prime[bisect_left(prime,x-pre)-1]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000\n",
    "isPrime = [True]*(1001)\n",
    "prime = [0]\n",
    "for i in range(2,N+1):\n",
    "    if(isPrime[i]):\n",
    "        prime.append(i)\n",
    "        x = i \n",
    "        while(i*x <= N):\n",
    "            isPrime[i*x] = False\n",
    "            x += 1\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            if(num <= pre):\n",
    "                return False\n",
    "            left, right = 0, len(prime) - 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(prime[mid] >= num - pre):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if(right < 0):\n",
    "                return False\n",
    "            pre = num - prime[right]\n",
    "            \n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 埃氏筛\n",
    "MX = 10 ** 3 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "primes.extend((MX, MX))  # 保证下面下标不会越界\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        mn = nums[0]\n",
    "        for i, x in enumerate(primes):\n",
    "            if x < nums[0]:\n",
    "                if nums[0] - x < mn:\n",
    "                    mn = nums[0] - x\n",
    "            else:\n",
    "                break\n",
    "        nums[0] = mn\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                return False\n",
    "            ans = nums[i]\n",
    "            for j, x in enumerate(primes):\n",
    "                if x < nums[i]:\n",
    "                    mn = nums[i - 1] + 1\n",
    "                    d = nums[i] - x\n",
    "                    if d >= mn:\n",
    "                        ans = d\n",
    "                    else:\n",
    "                        break                    \n",
    "                else:\n",
    "                    break\n",
    "            nums[i] = ans\n",
    "        flag = True\n",
    "        for x, y in pairwise(nums):\n",
    "            if y - x == 0: \n",
    "                flag = False\n",
    "                break\n",
    "        return nums == sorted(nums) and flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 1000 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] >= nums[i + 1]:\n",
    "                j = bisect_left(primes, nums[i] - nums[i + 1] + 1)\n",
    "                if j == len(primes):\n",
    "                    return False\n",
    "                if primes[j] >= nums[i]:\n",
    "                    return False\n",
    "                nums[i] -= primes[j]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            if nums[i]>=nums[i+1]:\n",
    "                F=1\n",
    "                for p in primes:\n",
    "                    if p>=nums[i]:\n",
    "                        break\n",
    "                    if nums[i]-p<nums[i+1]:\n",
    "                            nums[i]-=p\n",
    "                            F=0\n",
    "                            break\n",
    "                if F:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000\n",
    "isPrime = [True]*(1001)\n",
    "prime = [0]\n",
    "for i in range(2,N+1):\n",
    "    if(isPrime[i]):\n",
    "        prime.append(i)\n",
    "        x = i \n",
    "        while(i*x <= N):\n",
    "            isPrime[i*x] = False\n",
    "            x += 1\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            if(num <= pre):\n",
    "                return False\n",
    "            left, right = 0, len(prime) - 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(prime[mid] >= num - pre):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if(right < 0):\n",
    "                return False\n",
    "            pre = num - prime[right]\n",
    "            \n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        # def find_prime(n):\n",
    "        #     tar = [1] * (n + 1)\n",
    "        #     prime = []\n",
    "        #     for i in range(2, n + 1):\n",
    "        #         if tar[i]: prime.append(i)\n",
    "        #         for p in prime:\n",
    "        #             if p * i <= n: tar[p * i] = 0\n",
    "        #             else: break\n",
    "        #             if i % p == 0: break\n",
    "        #     return prime\n",
    "        # prime = find_prime(1000)\n",
    "        # # print(prime)\n",
    "        prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            diff = nums[i] - nums[i + 1]\n",
    "            if diff >= 0:\n",
    "                l, r = -1, len(prime)\n",
    "                while l + 1 < r:\n",
    "                    m = (l + r) // 2\n",
    "                    if prime[m] <= diff: l = m\n",
    "                    else: r = m\n",
    "                if r < len(prime) and prime[r] < nums[i]: nums[i] -= prime[r]\n",
    "                else: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        首先构造质数数组，存放范围内的所有质数，采用埃氏筛的方法，具体参见 204 题：计数质数（https://leetcode.cn/problems/count-primes/submissions/479534809/）\n",
    "        题目要求严格递增，反向遍历，如果前一个数字大于当前数字，那么前一个数字需要减小，至少要减去二者的差\n",
    "        再通过二分查找在质数数组中找到大于前一个数字和当前数字之差的第一个数，判断他是否超过前一个数字，超过了答案不成立，直接返回 false，没超过就减去后继续遍历\n",
    "        \"\"\"\n",
    "\n",
    "        # 只有一个元素已经满足题意\n",
    "        if len(nums) == 1:\n",
    "            \n",
    "            return True\n",
    "\n",
    "        # 创建一个小于 max(nums) 的质数数组\n",
    "        prime_nums = self.get_prime_nums(max(nums))\n",
    "\n",
    "        # 质数数组不存在\n",
    "        if len(prime_nums) == 0:\n",
    "            \n",
    "            return False\n",
    "\n",
    "        for i in range(len(nums) - 1, 0, -1):\n",
    "\n",
    "            if nums[i - 1] >= nums[i]:\n",
    "\n",
    "                p = self.binary_search(prime_nums, nums[i - 1] - nums[i])\n",
    "\n",
    "                if p == -1 or p >= nums[i - 1]:\n",
    "\n",
    "                    return False\n",
    "\n",
    "                else:\n",
    "\n",
    "                    nums[i - 1] -= p\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "    def get_prime_nums(self, num):\n",
    "        \"\"\"\n",
    "        埃氏筛方法创建比 num 小的质数数组\n",
    "        \"\"\"\n",
    "\n",
    "        # is_prime[i] 表示数 i 是不是质数，如果是质数则为 1，否则为 0\n",
    "        is_prime = [1 for _ in range(num)]\n",
    "\n",
    "        prime_nums = []\n",
    "\n",
    "        for i in range(2, num):\n",
    "\n",
    "            if is_prime[i] == 1:\n",
    "\n",
    "                prime_nums.append(i)\n",
    "\n",
    "                if i * i < num:\n",
    "\n",
    "                    for j in range(i * i, num, i):\n",
    "\n",
    "                        is_prime[j] = 0\n",
    "\n",
    "        return prime_nums\n",
    "\n",
    "    def binary_search(self, nums, target):\n",
    "        \"\"\"\n",
    "        二分查找，找到比 target 大的第一个数\n",
    "        \"\"\"\n",
    "\n",
    "        if target >= max(nums):\n",
    "            return -1\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "\n",
    "        while left <= right:\n",
    "\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            if(nums[mid] <= target):\n",
    "\n",
    "                left = mid + 1\n",
    "\n",
    "            else:\n",
    "\n",
    "                right = mid - 1\n",
    "\n",
    "        return nums[left]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import copy\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        primes=iter([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997])\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            if nums[i]>=nums[i+1]:\n",
    "                _primes=copy(primes)\n",
    "                F=1\n",
    "                try:\n",
    "                    while (p:=next(_primes))<nums[i]:\n",
    "                        if nums[i]-p<nums[i+1]:\n",
    "                            nums[i]-=p\n",
    "                            F=0\n",
    "                            break\n",
    "                except:\n",
    "                    return False\n",
    "                if F:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        N = 2000\n",
    "        isPrime = [1] * N\n",
    "        primes = []\n",
    "        for i in range(2, N):\n",
    "            if isPrime[i]:\n",
    "                primes.append(i)\n",
    "            for j in range(len(primes)):\n",
    "                if i * primes[j] >=N:\n",
    "                    break \n",
    "                isPrime[i * primes[j]] = 0\n",
    "                if  i% primes[j]==0:\n",
    "                    break \n",
    "        \n",
    "        n = len(nums)\n",
    "        m = len(primes)\n",
    "        for i in range(n-2,-1, -1):\n",
    "            if nums[i] < nums[i+1]:\n",
    "                continue \n",
    "            else:\n",
    "                for j in range(m):\n",
    "                    if nums[i] - primes[j] < nums[i+1]:\n",
    "                        nums[i] -= primes[j]\n",
    "                        break \n",
    "                if nums[i] <= 0:\n",
    "                    return False \n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        primes_lst = [1] * 1001\n",
    "        primes_lst[:3] = [0, 0, 1]\n",
    "        for i in range(2, int(math.sqrt(1001)) + 1):\n",
    "            if primes_lst[i]:\n",
    "                primes_lst[i ** 2::i] = [0] * len(primes_lst[i ** 2::i])\n",
    "        primes = [i for i in range(1001) if primes_lst[i]]\n",
    "        stk = []\n",
    "        for num in nums:\n",
    "            if not stk:\n",
    "                idx = bisect.bisect_left(primes, num)\n",
    "                if idx > 0:\n",
    "                    stk.append(num - primes[idx - 1])\n",
    "                elif idx == 0:\n",
    "                    stk.append(num)\n",
    "            else:\n",
    "                tmp = num - stk[-1]\n",
    "                idx = bisect.bisect_left(primes, tmp)\n",
    "                if idx > 0:\n",
    "                    stk.append(num - primes[idx - 1])\n",
    "                else:\n",
    "                    if num <= stk[-1]:\n",
    "                        return False\n",
    "                    else:\n",
    "                        stk.append(num)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primeSubOperation(self, nums: List[int]) -> bool:\n",
    "        primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            if nums[i]>=nums[i+1]:\n",
    "                F=1\n",
    "                for p in primes:\n",
    "                    if p>=nums[i]:\n",
    "                        break\n",
    "                    if nums[i]-p<nums[i+1]:\n",
    "                            nums[i]-=p\n",
    "                            F=0\n",
    "                            break\n",
    "                if F:\n",
    "                    return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
